//多数元素
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        // 快速选择
        qsort(nums, 0, n - 1, n / 2);

        return nums[n / 2];
    }
    void qsort(vector<int>& nums, int l, int r, int k) {
        if (l >= r)
            return;
        int left = l - 1;
        int right = r + 1;
        int i = l;
        int target = nums[rand() % (r - l + 1) + l];
        while (i < right) {
            if (nums[i] < target)
                swap(nums[i++], nums[++left]);
            else if (nums[i] == target)
                i++;
            else
                swap(nums[i], nums[--right]);
        }
        if (left >= k)
            qsort(nums, l, left, k);
        else if (k >= right)
            qsort(nums, right, r, k);
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int can;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (!count) {
                can = nums[i];
            }
            if (nums[i] != can) {
                count--;
            } else
                count++;
        }
        return can;
    }
};

//最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        int maxsize = 1;
        int posx = 0, posy = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    if (j - i == 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (maxsize < (j - i + 1)) {
                            maxsize = j - i + 1;
                            posx = i;
                            posy = j;
                        }
                    }
                }
            }
        }

        return s.substr(posx, maxsize);
    }
};